<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
            滑动窗口--固定滑动窗口
            时间复杂度：O(n)，并不是两个循环就是O(n)，每个元素至多进去一次，出来一次，就是O(n * 2) 也就是O(n)
            空间复杂度：O(1)
        */
      var checkInclusion = function (s1, s2) {
        let left = 0;
        let right = 0;
        let valid = 0;
        const need = new Map();
        const window = new Map();
        for (const str of s1) {
          need.set(str, (need.get(str) || 0) + 1);
        }

        while (right < s2.length) {
          const c = s2[right];
          right++;
          // 1. 更新window里面的值，如果该字符和need里面的数量一致了，要更新valid值
          if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) === need.get(c)) {
              valid++;
            }
          }
          // 2. 当字符串的长度和s1子串长度一样时，要暂停扩大，开始缩小
          while (right - left >= s1.length) {
            if (valid === need.size) {
              // 4. 结果应该在缩小窗口的时候进行更新
              return true;
            }
            let d = s2[left];
            left++;
            // 3. 执行left++，缩小窗口后，要更新window的值，同时要根据需要更新valid的值
            if (need.has(d)) {
              if (need.get(d) === window.get(d)) {
                valid--;
              }
              window.set(d, (window.get(d) || 0) - 1);
            }
          }
        }
        return false;
      };

      //   console.log(checkInclusion("ab", "eidbaooo"));
      console.log(checkInclusion("ab", "eidboaoo"));
    </script>
  </body>
</html>
